package com.learning.algorithm.sort.simpleSort;

import com.learning.algorithm.sort.ArraysUtil;
import com.learning.algorithm.sort.CheckSort;
import com.learning.algorithm.sort.IntArraySort;
import com.learning.algorithm.sort.divideAndConquer.MergeSort;

import java.util.Arrays;

/**
 * @Author: lishi
 * @Description: ${description}
 * @Date: 2021/11/22 14:08
 */
public class Insert_ShellSort implements IntArraySort {
    public static void shellSort(int[] arrays) {
        for (int gap = arrays.length / 2; gap > 0; gap = gap / 2) {
//            System.out.println("=====================gap 为 ： " + gap + "的排序start！=====================");
            for (int j = 0; j < gap; j++) {
                for (int k = j + gap; k < arrays.length; k += gap) {
                    for (int m = k - gap; m >= 0; m -= gap) {
                        if (arrays[m] <= arrays[m + gap]) {
                            break;
                        }
                        ArraysUtil.swap(arrays, m, m + gap);
                    }
//                    System.out.println("gap为  " + gap + "的第 " + k + "个数字排序后结果 ： " + Arrays.toString(arrays));
                }
//                System.out.println("gap为  " + gap + "的第 " + (j + 1) + "次排序后结果 ： " + Arrays.toString(arrays));
            }
//            System.out.println("=====================gap 为 ： " + gap + "的排序end！=====================");
        }
    }

    public static void main(String[] args) {
        int length = 10000000;
        int[] originArrays = ArraysUtil.genNoDuplicateIntArray(length);
        int[] cloneArrays = new int[length];
        int[] cloneArrays2 = new int[length];
        int[] cloneArrays3 = new int[length];
        int[] cloneArrays4 = new int[length];
        System.arraycopy(originArrays, 0, cloneArrays, 0, length);
//        System.arraycopy(originArrays, 0, cloneArrays2, 0, length);
//        System.arraycopy(originArrays, 0, cloneArrays3, 0, length);
        System.arraycopy(originArrays, 0, cloneArrays4, 0, length);

        long mergeSortStartTime = System.currentTimeMillis();
        cloneArrays4 = MergeSort.mergeSort(cloneArrays4);
        System.out.println(length + " length array mergeSort cost " + (System.currentTimeMillis() - mergeSortStartTime) + " ms");

        long shellSortStartTime = System.currentTimeMillis();
        shellSort(cloneArrays);
        System.out.println(length + " length array shellSort cost " + (System.currentTimeMillis() - shellSortStartTime) + " ms");

//        long insertSort1StartTime = System.currentTimeMillis();
//        InsertSort.insertSort(cloneArrays2);
//        System.out.println(length + " length array insertSort cost " + (System.currentTimeMillis() - insertSort1StartTime) + " ms");
//
//        long insertSort2StartTime = System.currentTimeMillis();
//        InsertSort.insertSort2(cloneArrays3);
//        System.out.println(length + " length array insertSort2 cost " + (System.currentTimeMillis() - insertSort2StartTime) + " ms");

        System.out.println(CheckSort.checkSortResult(originArrays, cloneArrays));
//        System.out.println(CheckSort.checkSortResult(originArrays, cloneArrays2));
//        System.out.println(CheckSort.checkSortResult(originArrays, cloneArrays3));
        System.out.println(CheckSort.checkSortResult(originArrays, cloneArrays4));
    }

    public int[] sort(int[] arrays) {
        shellSort(arrays);
        return arrays;
    }

    public String getDesc() {
        return "希尔排序";
    }
}
